package lc.q101_150;

import lc.TreeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

public class Q113 {

    private final Deque<Integer> deque = new LinkedList<>();
    private final List<List<Integer>> results = new ArrayList<>();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        dfs(root, targetSum);
        return results;
    }

    private void dfs(TreeNode treeNode, int targetSum) {
        if (treeNode == null) {
            return;
        }
        int rootVal = treeNode.val;
        deque.offerLast(rootVal);
        targetSum -= rootVal;
        if (treeNode.left == null && treeNode.right == null && targetSum == 0) {
            results.add(new LinkedList<>(deque));
        }
        dfs(treeNode.left, targetSum);
        dfs(treeNode.right, targetSum);
        deque.pollLast();
    }

}
